package com.maduar.demo.util;

import com.google.common.collect.Lists;

import java.util.List;

/**
 * Description:
 *
 * @author danny.pang danny.pang@ebizprise.com
 * @date 2020-08-31 18:09
 */
public class Graph {

    // 标记当前节点是否访问过
    boolean[] vis;
    int num;

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        num = 0;
        vis = new boolean[n];
        dfs(rooms, 0);
        return num == n;
    }

    public void dfs(List<List<Integer>> rooms, int x) {
        vis[x] = true;
        num++;
        for (int it : rooms.get(x)) {
            if (!vis[it]) {
                dfs(rooms, it);
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph();

        // [[1],[2],[3],[]]  true

        List<List<Integer>> list = Lists.newArrayList();
        list.add(Lists.newArrayList(1));
        list.add(Lists.newArrayList(2));
        list.add(Lists.newArrayList(3));
        list.add(Lists.newArrayList());

        boolean resultBool = graph.canVisitAllRooms(list);

        System.out.println("resultBool: " + resultBool);


        // [[1,3],[3,0,1],[2],[0]] false
        List<List<Integer>> list2 = Lists.newArrayList();
        list2.add(Lists.newArrayList(1,3));
        list2.add(Lists.newArrayList(3,0,1));
        list2.add(Lists.newArrayList(2));
        list2.add(Lists.newArrayList(0));

        boolean result2Bool = graph.canVisitAllRooms(list2);

        System.out.println("result2Bool: " + result2Bool);
    }
}
